import javax.swing.text.html.parser.Entity;
import java.util.*;

//输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
// 输出：["JFK","MUC","LHR","SFO","SJC"]
public class ReconstructItinerary0104_332 {
    LinkedList<String> result = new LinkedList<>();

    // Map<出发机场, map<到达机场, 航班次数>> targets
    Map<String, Map<String, Integer>> targets = new HashMap<String,Map<String,Integer>>();

    public List<String> findItinerary(List<List<String>> tickets) {

        //初始化targets
        // 把tickets的所有航班信息转换为：Map<出发机场, map<到达机场, 航班次数>> 的map集合
        for (List<String> ticket : tickets) { // ticket: ["MUC","LHR"]
            Map<String,Integer> temp = new TreeMap<>(); //TreeMap 升序Map，底层红黑树，保证了根据出发机场获取的map<到达机场, 航班次数>是有序的
            if(targets.containsKey(ticket.get(0))){
                 temp = targets.get(ticket.get(0));
                 temp.put(ticket.get(1),temp.getOrDefault(ticket.get(1),0) + 1);
            }else {
                temp.put(ticket.get(1),1);
            }
            targets.put(ticket.get(0),temp);
        }

        //初始出发机场
        result.add("JFK");

        // 传入机票的张数，用于终止条件判断
        backTracking(tickets.size());
        return result;
    }

    // 由于根据出发机场获取的map<到达机场, 航班次数>是有序的，所以找到的第一个路径就是需要的字典排序最小的行程组合。
    // 所以设置布尔类型返回值，找到结果停止遍历所有树，立马返回答案。
    private boolean backTracking(int size) {
        if(size+1 == result.size()) return true; //票数比站点少1.

        //获取下一阶段机票的起始站点
        String start = result.getLast();

        // 根据起始位置 确定能找到出发地为起始位置的机票
        if(targets.containsKey(start)){
            // 遍历该起始位置能到达的entry键值对<到达机场, 航班次数>
            for (Map.Entry<String, Integer> tar : targets.get(start).entrySet()) {
                // count为 该<起始位置, 到达机场> 的机票张数
                int count = tar.getValue();
                // count＞0（有票）的情况
                if(count > 0) {
                    result.add(tar.getKey());
                    tar.setValue(count - 1);
                    if(backTracking(size)) return true;
                    tar.setValue(count);
                    result.removeLast();
                }
            }
        }
        return false;
    }
}
